3강에 오신 것을 환영합니다 인공지능 개념 (PolyU COMP5511). 이번 세션에서는 단일 에이전트 경로 탐색에서 적대적 탐색으로 전환하며, 에이전트가 경쟁적인 다중 에이전트 환경에서 작동하는 방식을 다룹니다. 또한 제약 조건 만족 문제(CSPs)을 소개합니다. 이는 경로가 아닌 특정 제약 조건 집합을 만족하는 상태를 찾는 것이 목표인 패러다임입니다.

핵심 개념

• 적대적 탐색: 지능적인 상대방에 대해 합리적인 결정을 내리기 위한 미니맥스 및 알파-베타 가지치기 와 같은 알고리즘에 중점을 둡니다.
• 몬테카를로 트리 탐색(MCTS): 확률적 의사결정을 탐구하며, 알파고와 같은 현대 게임 AI의 기반이 됩니다.
• 제약 조건 만족: 변수, 도메인, 제약 조건을 사용하여 문제를 모델링하며, 백트래킹 및 로컬 탐색와 같은 현대 게임 AI의 기반이 됩니다.

복잡도 분석

적대적 환경에서 탐색 공간의 복잡도는 주로 게임의 분기 계수 $b$ 와 깊이 $d$에 의해 결정되며, 계산 비용은 다음과 같습니다: $$O(b^d)$$ 이러한 지수적 증가는 알파-베타 가지치기와 같은 효율적인 가지치기 전략을 필요로 합니다.